{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #游乐园的迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #geometry #array #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #几何 #数组 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: visitOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #游乐园的迷宫"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>小王来到了游乐园，她玩的第一个项目是模拟推销员。有一个二维平面地图，其中散布着 <code>N</code> 个推销点，编号 <code>0</code> 到 <code>N-1</code>，不存在三点共线的情况。每两点之间有一条直线相连。游戏没有规定起点和终点，但限定了每次转角的方向。首先，小王需要先选择两个点分别作为起点和终点，然后从起点开始访问剩余 <code>N-2</code> 个点恰好一次并回到终点。访问的顺序需要满足一串给定的长度为 <code>N-2</code> 由 <code>L</code> 和 <code>R</code> 组成的字符串 <code>direction</code>，表示从起点出发之后在每个顶点上转角的方向。根据这个提示，小王希望你能够帮她找到一个可行的遍历顺序，输出顺序下标（若有多个方案，输出任意一种）。可以证明这样的遍历顺序一定是存在的。</p>\n",
    "\n",
    "<p><img alt=\"Screenshot 2020-03-20 at 17.04.58.png\" src=\"https://pic.leetcode-cn.com/595b60797d4a461287864a8cd05bba1d3b8760104ff83f43b902fd68477be9c3-Screenshot%202020-03-20%20at%2017.04.58.png\" style=\"max-height:500px\" /></p>\n",
    "\n",
    "<p>（上图：A-&gt;B-&gt;C 右转； 下图：D-&gt;E-&gt;F 左转）</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>points = [[1,1],[1,4],[3,2],[2,1]], direction = \"LL\"</code></p>\n",
    "\n",
    "<p>输入：<code>[0,2,1,3]</code></p>\n",
    "\n",
    "<p>解释：[0,2,1,3] 是符合\"LL\"的方案之一。在 [0,2,1,3] 方案中，0-&gt;2-&gt;1 是左转方向， 2-&gt;1-&gt;3 也是左转方向 <img alt=\"图片.gif\" src=\"https://pic.leetcode-cn.com/c01c1efc423b916267c2a3a170266c925c368d62afa047c267cc1020970e55d9-%E5%9B%BE%E7%89%87.gif\" style=\"max-height:300px\" /></p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<blockquote>\n",
    "<p>输入：<code>points = [[1,3],[2,4],[3,3],[2,1]], direction = \"LR\"</code></p>\n",
    "\n",
    "<p>输入：<code>[0,3,1,2]</code></p>\n",
    "\n",
    "<p>解释：[0,3,1,2] 是符合\"LR\"的方案之一。在 [0,3,1,2] 方案中，0-&gt;3-&gt;1 是左转方向， 3-&gt;1-&gt;2 是右转方向</p>\n",
    "</blockquote>\n",
    "\n",
    "<p><strong>限制：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>3 &lt;= points.length &lt;= 1000 且 points[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= points[i][0],points[i][1] &lt;= 10000</code></li>\n",
    "\t<li><code>direction.length == points.length - 2</code></li>\n",
    "\t<li><code>direction 只包含 \"L\",\"R\"</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [you-le-yuan-de-mi-gong](https://leetcode.cn/problems/you-le-yuan-de-mi-gong/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [you-le-yuan-de-mi-gong](https://leetcode.cn/problems/you-le-yuan-de-mi-gong/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[1,4],[3,2],[2,1]]\\n\"LL\"', '[[1,3],[2,4],[3,3],[2,1]]\\n\"LR\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sub(self, a, b): # 求点 a 到点 b 的向量\n",
    "        return [a[0]-b[0], a[1]-b[1]]\n",
    "    \n",
    "    def cross(self, a, b):  # 求向量 a 到向量 b 的向量叉积\n",
    "        return a[0] * b[1] - a[1] * b[0]\n",
    "    \n",
    "    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:\n",
    "        n = len(points)\n",
    "        used = [False] * n  # 记录点的遍历情况， False未遍历 / True已遍历\n",
    "        order = [] # 记录返回结果\n",
    "        \n",
    "        # 查找最左的点作为 起始点\n",
    "        start = 0\n",
    "        for i in range(0,n):\n",
    "            if points[i][0] < points[start][0]:\n",
    "                start = i\n",
    "        used[start] =True\n",
    "        order.append(start)\n",
    "        \n",
    "        for i in direction:\n",
    "            nxt = -1\n",
    "            if i=='L':\n",
    "                # 转向方向为 L，选择相对方向最右的点\n",
    "                for j in range(0,n):\n",
    "                    if not used[j]:\n",
    "                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) <0 :\n",
    "                            nxt = j\n",
    "            else:\n",
    "                # 转向方向为 R，选择相对方向最左的点\n",
    "                for j in range(0,n):\n",
    "                    if not used[j]:\n",
    "                        if nxt==-1 or self.cross(self.sub(points[nxt],points[start]), self.sub(points[j],points[start])) >0 :\n",
    "                            nxt = j\n",
    "            # 返回结果加入选择的点，更新下一次转向的起点\n",
    "            used[nxt] = True\n",
    "            order.append(nxt)\n",
    "            start = nxt\n",
    "        \n",
    "        # 添加最后一个剩余点\n",
    "        for i in range(0,n):\n",
    "            if not used[i]:\n",
    "                order.append(i)\n",
    "        return order"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:\n",
    "        start, start_x = -1, 10001\n",
    "        for index, [x, y] in enumerate(points):\n",
    "            if x < start_x:\n",
    "                start_x = x\n",
    "                start = index\n",
    "        ans = [start]\n",
    "        used = {start}\n",
    "        n = len(points)\n",
    "        for letter in direction:\n",
    "            best_i, best_vector = -1, [0, 0]\n",
    "            for i in range(n):\n",
    "                if i in used:\n",
    "                    continue\n",
    "                cur_vector = [points[i][0] - points[ans[-1]][0], points[i][1] - points[ans[-1]][1]]\n",
    "                cross_product = best_vector[0] * cur_vector[1] - best_vector[1] * cur_vector[0]\n",
    "                if best_i < 0 or (letter == 'L' and cross_product < 0) or (letter == 'R' and cross_product > 0):\n",
    "                    best_i = i\n",
    "                    best_vector = cur_vector\n",
    "            ans.append(best_i)\n",
    "            used.add(best_i)\n",
    "        for i in range(n):\n",
    "            if i not in used:\n",
    "                ans.append(i)\n",
    "                break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:\n",
    "        # 贪心\n",
    "        # 如果下一次要左转 'L'，则走到最右侧的点，此时所有的点都在左侧，同理\n",
    "        # 如果下一次要右转 'R'，则走到最左侧的点，此时所有的点都在右侧\n",
    "        # 那么关于起点的选择，参照上述规则，选择极点\n",
    "        def vectorDirc(a, b, o):\n",
    "            # return direction of a -> b, o is original point of a & b\n",
    "            xo, yo = o\n",
    "            xa, ya = a[0] - xo, a[1] - yo\n",
    "            xb, yb = b[0] - xo, b[1] - yo\n",
    "            return 'L' if xa*yb - xb*ya > 0 else 'R'\n",
    "        # \n",
    "        rest = {tuple(pt) : i for i, pt in enumerate(points)}\n",
    "        # 设置起点为x最大或x最小的点，x最大和x最小的点都在凸包上\n",
    "        # 当第一步要向右走时，原点选x最大，第二个点会选左侧最小，于是所有点都在右侧，反之同理\n",
    "        start = max(points) if direction[0] == 'R' else min(points)\n",
    "        ans = [rest.pop(tuple(start))]\n",
    "        # \n",
    "        x_cur, y_cur = 0, 0\n",
    "        for i in range(len(direction)):\n",
    "            _dir = direction[i]\n",
    "            for xi, yi in rest.keys():\n",
    "                # 找到与下一次转向的反方向最远向量 e.g. 下一步_dir要右转，那么本次找到最左侧\n",
    "                if not x_cur or vectorDirc([x_cur, y_cur], [xi, yi], points[ans[-1]]) != _dir:\n",
    "                    x_cur, y_cur = xi, yi\n",
    "            ans.append(rest.pop((x_cur,y_cur)))\n",
    "            x_cur, y_cur = 0, 0\n",
    "        ans.append(list(rest.values())[0])\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef visitOrder(self, points, direction):\n",
    "\t\tpool = [[x, y, i] for i, [x, y] in enumerate(points)]\n",
    "\t\tpool.sort()\n",
    "\t\tx0, y0, i0 = pool[0]\n",
    "\t\tks = [[(float('inf') if x == x0 else (y - y0) / (x - x0)), i] for x, y, i in pool[1:]]\n",
    "\t\tks.sort()\n",
    "\t\tans = [i0, ks[0][1]] if direction[0] == 'L' else [i0, ks[-1][1]]\n",
    "\t\tused = set(ans)\n",
    "\t\tfor i in range(1, len(direction)):\n",
    "\t\t\tcur = [[self.calc(points[ans[-2]], points[ans[-1]], [x, y]), i] for x, y, i in pool if i not in used]\n",
    "\t\t\tcur.sort(reverse = (direction[i] == direction[i - 1]))\n",
    "\t\t\tans.append(cur[0][1])\n",
    "\t\t\tused.add(cur[0][1])\n",
    "\t\treturn ans + [i for x, y, i in pool if i not in used]\n",
    "\t\n",
    "\tdef calc(self, p1, p2, p3): #向量夹角余弦值\n",
    "\t\tdx1 = p2[0] - p1[0]\n",
    "\t\tdx2 = p3[0] - p2[0]\n",
    "\t\tdy1 = p2[1] - p1[1]\n",
    "\t\tdy2 = p3[1] - p2[1]\n",
    "\t\treturn (dx1 * dx2 + dy1 * dy2) / math.sqrt(dx1 * dx1 + dy1 * dy1) / math.sqrt(dx2 * dx2 + dy2 * dy2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def visitOrder(self, points: List[List[int]], direction: str) -> List[int]:\n",
    "        n = len(points)\n",
    "        ans = []\n",
    "        v = [1]*n\n",
    "        def judge(s:int,m:int,e:int,tot:int)->bool:\n",
    "            l1x, l1y = points[m][0]-points[s][0],points[m][1]-points[s][1]\n",
    "            l2x, l2y = points[e][0]-points[m][0],points[e][1]-points[m][1]\n",
    "            d = l1x*l2y-l1y*l2x\n",
    "            if d >0 and direction[tot]=='L':\n",
    "                return True\n",
    "            if d<0 and direction[tot]=='R':\n",
    "                return True\n",
    "            return False\n",
    "            \n",
    "        def dfs(s:int,m:int,e:int,tot:int)->bool:\n",
    "            if tot == n:\n",
    "                return True\n",
    "            if tot==0:\n",
    "                for i in range(n):\n",
    "                    v[i] = 0\n",
    "                    if dfs(n,n,i,1):\n",
    "                        ans.append(i)\n",
    "                        return True\n",
    "                    v[i] = 1\n",
    "            if tot == 1:\n",
    "                for i in range(n):\n",
    "                    if v[i]:\n",
    "                        v[i] = 0\n",
    "                        if dfs(n,e,i,2):\n",
    "                            ans.append(i)\n",
    "                            return True\n",
    "                        v[i] = 1\n",
    "            if tot >= 2:\n",
    "                flag = 0\n",
    "                for i in range(n):\n",
    "                    if v[i] and judge(m,e,i,tot-2):\n",
    "                        flag = 1\n",
    "                        v[i] = 0\n",
    "                        if dfs(m,e,i,tot+1):\n",
    "                            ans.append(i)\n",
    "                            return True\n",
    "                        v[i] = 1\n",
    "                if not flag:\n",
    "                    return False   \n",
    "                    \n",
    "        if dfs(n,n,n,0):\n",
    "            ans.reverse()\n",
    "            return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
